import collections
from typing import List


class Solution(object):
    def orangesRotting(self, grid):
        R, C = len(grid), len(grid[0])

        # queue - all starting cells with rotting oranges
        queue = collections.deque()
        for r, row in enumerate(grid):
            for c, val in enumerate(row):
                if val == 2:
                    queue.append((r, c, 0))

        def neighbor(r, c):
            for nr, nc in ((r-1,c),(r,c-1),(r+1,c),(r,c+1)):
                if 0 <= nr < R and 0 <= nc < C:
                    yield nr, nc

        d = 0 #如果输入的是[[0]] 不会经过下面的循环 需要一个数字来返回， 同时也需要一个外部变量来记录depth
        while queue:
            r, c, d = queue.popleft()
            for nr, nc in neighbor(r, c):
                if grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    queue.append((nr, nc, d+1))

        if any(1 in row for row in grid):
            return -1
        return d

# 作者：LeetCode-Solution
# 链接：https://leetcode-cn.com/problems/rotting-oranges/solution/fu-lan-de-ju-zi-by-leetcode-solution/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


#BFS
# 给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
#
# 规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
#
# 请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
# 给定下面的 5x5 矩阵:
#
#   太平洋 ~   ~   ~   ~   ~
#        ~  1   2   2   3  (5) *
#        ~  3   2   3  (4) (4) *
#        ~  2   4  (5)  3   1  *
#        ~ (6) (7)  1   4   5  *
#        ~ (5)  1   1   2   4  *
#           *   *   *   *   * 大西洋
#
# 返回:
#
# [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).


class Solution:
    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:
        # 一开始自己的思路是 对于每一个点都用BFS模拟水流流动 就可以知道能不能流到两个大洋
        # 觉得这样做有太多重复 那么要想dp一样记录一下已经出结果的点 再次访问的时候就不重复计算了

        # 看了题解后发现 可以逆向思维 由边缘向内扩散 这样被两个大洋扩散到的点就是满足要求的点了

        res = []
        ROW = len(matrix)
        if ROW == 0:
            return res
        COL = len(matrix[0])

        def helper(r, c):
            for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
                if 0 <= nr < ROW and 0 <= nc < COL:
                    yield nr, nc

        destn = [[[] for _ in range(COL)] for _ in range(ROW)]

        queue = collections.deque()
        for ocean in ('Pacific', 'Atlantic'):
            queue.clear()

            if ocean == 'Pacific':
                for i in range(ROW):
                    queue.append((i, 0, matrix[i][0]))
                for i in range(COL):
                    queue.append((0, i, matrix[0][i]))
            elif ocean == 'Atlantic':
                for i in range(ROW):
                    queue.append((i, COL - 1, matrix[i][COL - 1]))
                for i in range(COL):
                    queue.append((ROW - 1, i, matrix[ROW - 1][i]))

            while queue:
                r, c, val = queue.popleft()
                destn[r][c].append(ocean)

                for nr, nc in helper(r, c):
                    if matrix[nr][nc] >= val and (ocean not in destn[nr][nc]):  # 老是忘记防止死循环
                        queue.append((nr, nc, matrix[nr][nc]))

        for r, row in enumerate(destn):
            for c, d in enumerate(row):
                if 'Pacific' in d and 'Atlantic' in d:
                    res.append([r, c])

        return res